from typing import *


# 每个黑点作为一角的四个方形里面，每个方形有几个黑点
# 2个黑点的会被重复计算两次，3个会被重复计算三次，4个会被重复计算四次
class Solution:

    def countBlackBlocks(self, m: int, n: int,
                         coordinates: List[List[int]]) -> List[int]:
        s = set()

        ans = [0] * 5

        g = [[(-1, -1), (0, -1), (-1, 0)], [(-1, 0), (-1, 1), (0, 1)],
             [(0, -1), (1, -1), (1, 0)], [(0, 1), (1, 1), (1, 0)]]

        def hash(x, y):
            return x * n + y

        for x, y in coordinates:
            s.add(hash(x, y))

        for x, y in coordinates:
            for r in g:
                cnt, o = 1, True
                for a, b in r:
                    p, q = a + x, b + y
                    if p < 0 or p == m or q < 0 or q == n:
                        o = False
                    if hash(p, q) in s:
                        cnt += 1
                if o:
                    ans[cnt] += 1

        for i in range(2, 5):
            ans[i] //= i

        ans[0] = m * n - m - n + 1 - sum(ans)
        return ans


class Solution:

    def countBlackBlocks(self, m: int, n: int,
                         coordinates: List[List[int]]) -> List[int]:      
        s = set()

        def h(x, y):
            return x * n + y

        for x, y in coordinates:
            s.add(h(x, y))

        vis = set()

        ans = [0] * 5
        for x, y in coordinates:
            for i in range(max(x - 1, 0), min(x + 1, m - 1)):
                for j in range(max(y - 1, 0), min(y + 1, n - 1)):
                    if h(i, j) not in vis:
                        vis.add(h(i, j))
                        cnt = h(i, j) in s
                        for p, q in [(1, 0), (0, 1), (1, 1)]:
                            cnt += h(i + p, j + q) in s
                        ans[cnt] += 1
        ans[0] = m * n - m - n + 1 - sum(ans)
        return ans


s = Solution()
print(s.countBlackBlocks(m=3, n=3, coordinates=[[0, 0]]) == [3, 1, 0, 0, 0])
print(
    s.countBlackBlocks(m=3, n=3, coordinates=[[0, 0], [1, 1], [0, 2]]) ==
    [0, 2, 2, 0, 0])
